package dataStructure.List;

/**
 * OddAndEventList - TODO 描述.
 *
 * @author XY
 * @Date 2024/6/13
 */
public class OddAndEventList {
    public static void main(String[] args) {
        ListNode head = null,tail=null;
        for(int i=0;i<5;i++){
            ListNode cur = new ListNode(i+1);
            if(i==0) head=cur;
            if(tail!=null) tail.next=cur;
            tail=cur;
        }
        ListNode res = new OddAndEventList().oddEvenList(head);
    }
    public ListNode oddEvenList(ListNode head) {
        ListNode odd=null,event=null;
        if(head!=null) odd=head;
        else return head;
        ListNode oddTail = head;

        if(head.next!=null) event=head.next;
        else return head;
        ListNode eventTail = head.next;

        int idx=2;
        ListNode cur=event.next;
        while(cur!=null){
            idx++;
            if(idx%2==1){
                oddTail.next=cur;
                oddTail=cur;
            }else{
                eventTail.next=cur;
                eventTail=cur;
            }
            cur=cur.next;
        }
        oddTail.next=event;
        eventTail.next=null;
        return odd;
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
